/*
 * @Author: Thatcher Li
 * @Date: 2021-01-06 18:40:59
 * @LastEditors: Please set LastEditors
 * @LastEditTime: 2021-07-16 16:13:47
 * @Descripttion: 线性表、栈、队列、二叉树结点类型与通用方法
 */

#include <stdio.h>
#include <stdlib.h>
#define maxSize 5

/**
 * @description: 二叉树
 * @param {*}
 * @return {*}
 */
typedef struct BTNode{
    /* data */
    int data;
    struct BTNode *lchild;
    struct BTNode *rchild;
}BTNode;


/*==========================顺序表=================================*/

/**
 * @description: 顺序表
 * @param {*}
 * @return {*}
 */
typedef struct{
    /* data */
    int data[maxSize];
    int length;
}Sqlist;

/**
 * @description: 查找 x 将要插入的位置，假设顺序表示递增的
 * @param {Sqlist} l
 * @param {int} val
 * @return {*} 元素要插入的位置
 */
int sqlist_find_Elem(Sqlist *l,int val){
    int i;
    for (i = 0; i < l->length; i++){
        if(val < l->data[i]){
            return i;
        }
    }
    return i;
}

/**
 * @description: 顺序表元素插入
 * @param {Sqlist} *l
 * @param {int} index
 * @param {int} val
 * @return {*}
 */
int sqlist_insertElem(Sqlist *l,int index,int val){
    if(index < 0 || index > l->length || l->length == maxSize)
        return -1;  // 插入失败，传入的 index 非法
    for (int i = l->length-1; i >= index; i--){
        l->data[i+1] = l->data[i];  // 从后往前遍历到index，每个元素往后移一位
    }
    l->data[index] = val;
    ++(l->length);
    return 1;   // 插入成功
}


/**
 * @description: 顺序表元素删除
 * @param {Sqlist} *l
 * @param {int} index 将要删除元素的下标
 * @param {int} *e 被删除的元素值
 * @return {*} -1 删除失败，1 删除成功
 */
int sqlist_delElem(Sqlist *l,int index,int *e){
    if(index < 0 || index >= l->length) // 越界
        return -1;
    *e = l->data[index];
    for (int i = index+1; i < l->length; i++){// 从 index 遍历到顺序表结尾，每个元素往前移一位
        l->data[i-1] = l->data[i];
    }
    --(l->length);
    return 1;
}


/**
 * @description: 顺序表的逆置操作
 * @param {Sqlist} *l
 * @param {int} k，逆置 k 个元素
 * @return {*}
 */
void sqlist_reverse(Sqlist *l,int left, int right, int k){
    int temp;
    for (; left < k+left && left < right; left++,right--){
        temp = l->data[left];
        l->data[left] = l->data[right];
        l->data[right] = temp;
    }
}

/**
 * @description: 顺序表循环左移 k 个位置
 * @param {Sqlist} *l
 * @param {int} n
 * @param {int} k
 * @return {*}
 */
void sqlist_recycle_moveK(Sqlist *l,int n, int k){
    sqlist_reverse(l,0,k-1,k);
    sqlist_reverse(l,k,n-1,n-k);
    sqlist_reverse(l,0,n-1,n);
}


/**
 * @description: 顺序表的打印
 * @param {Sqlist} *l
 * @return {*}
 */
void sqlist_print(Sqlist *l){
    printf("顺序表元素数量：%d\n",l->length);
    printf("顺序表的元素：\n");
    for (int i = 0; i < l->length; i++){
        printf("%d\t",l->data[i]);
    }
    printf("\n");
}

/**
 * @description: 顺序表的初始化，注意 C 语言中整形(非静态变量)未初始化，那默认值就是堆栈里面的随机值
 * @param {*}
 * @return {*}
 */
void sqlist_init(Sqlist *l){
    l->length = 0;
}



/*==========================单链表(带头结点)=================================*/

/**
 * @description: 单链表
 * @param {*}
 * @return {*}
 */
typedef struct LNode{
    int data;
    struct LNode *next;
}LNode;


/**
 * @description: 单链表的初始化，尾插法，带头节点
 * @param {LNode} *lNode
 * @param {int} a
 * @param {int} n
 * @return {*}
 */

// 这里有个疑问， 这里传递的是指针，为什么实参的值不会随之改变，只能返回形参的值(传递是指针变量，并不是指针变量的地址)
LNode * link_init_tail(LNode *lNode,int a[],int n){
    LNode *p, *tail;   // p 用来指向新申请的节点，tail 始终指向 lNode 的尾节点
    lNode = (LNode *)malloc(sizeof(LNode)); //申请 lNode 的头结点空间
    lNode->next = NULL;
    tail = lNode;

    for (int i = 0; i < n; i++){ // 循环申请 n 个结点来接收数组 a 中的元素
        p = (LNode *)malloc(sizeof(LNode));
        p->data = a[i];
        tail->next = p;
        tail = p;
    }
    tail->next = NULL;
    return lNode;
}

/**
 * @description: 头插法建立单链表，带头节点
 * 头插法不断地将新结点插入链表的前端，因此建立的链表元素的次序和数组 a 中的元素的次序是相反的。
 * @param {LNode} *LNode
 * @param {int} a
 * @param {int} n
 * @return {*}
 */
LNode * link_init_head(LNode *lNode,int a[],int n){
    LNode *p;
    lNode = (LNode *)malloc(sizeof(LNode));
    lNode->next = NULL;

    for (int i = 0; i < n; i++){
        p = (LNode *)malloc(sizeof(LNode));
        p->data = a[i];
        p->next = lNode->next;
        lNode->next = p;
    }
    return lNode;
}


/**
 * @description: 删除第 i 个链表元素，头结点不能删除
 * @param {LNode} *lNode
 * @param {int} i
 * @return {*}
 */
void link_delElem(LNode *lNode,int i){
    int index = 0;
    while(lNode != NULL && lNode->next != NULL){
        if(index++ == i-1){
            LNode *del = lNode->next;
            lNode->next = lNode->next->next;
            free(del); // 注意释放 del 指针所指向节点的内存空间
            break;
        }
        lNode = lNode->next;
    }
}



/**
 * @description: 合并两个有序链表，合并之后还是单调递增的，尾插法的合并方法
 * @param {LNode} *L1
 * @param {LNode} *L2
 * @return {*}
 */
LNode * link_merge_asc(LNode *L1, LNode *L2){
    LNode *p1, *p2, *cur, *head;
    p1 = L1->next;
    p2 = L2->next;
    head = cur = L1;
    while (p1 != NULL && p2 != NULL){
        if(p1->data < p2->data){
            cur->next = p1;
            p1 = p1->next;
        }else{
            cur->next = p2;
            p2 = p2->next;
        }
        cur = cur->next;
    }
    if (p1){
        cur->next = p1;
    }
    if (p2){
        cur->next = p2;
    }
    
    return head;
}

/**
 * @description: 合并两个有序链表，合并之后是单调递减的，头插法的合并方法
 * @param {*}
 * @return {*}
 */
LNode * link_merge_des(LNode *L1, LNode *L2){
    LNode *p1, *p2, *cur = NULL, *temp;
    p1 = L1->next;
    p2 = L2->next;
    while (p1 != NULL && p2 != NULL){
        if(p1->data < p2->data){
            temp = p1;
            p1 = p1->next;
            temp->next = cur;
            cur = temp;
        }else{
            temp = p2;
            p2 = p2->next;
            temp->next = cur;
            cur = temp;
        }
    }
    while(p1 != NULL){
        temp = p1;
        p1 = p1->next;
        temp->next = cur;
        cur = temp;
    }
    while(p2 != NULL){
        temp = p2;
        p2 = p2->next;
        temp->next = cur;
        cur = temp;
    }
    L1->next = cur;
    return L1;
}

/**
 * @description: 单链表的打印
 * @param {LNode} *LNode
 * @return {*}
 */
void link_print(LNode *lNode){
    printf("单链表的元素：\n");
    lNode = lNode->next;
    while (lNode != NULL){
        printf("%d\t",lNode->data);
        lNode = lNode->next;
    }
    printf("\n");
}



/*==========================双链表(带头结点)=================================*/

/**
 * @description: 双链表
 * @param {*}
 * @return {*}
 */
typedef struct DLNode{
    int data;
    struct DLNode *prior;
    struct DLNode *next;
}DLNode;

/**
 * @description: 双链表的初始化，尾插法
 * @param {*}
 * @return {*}
 */
DLNode * dlink_init_tail(DLNode * dlNode, int a[], int n){
    dlNode = (DLNode *)malloc(sizeof(DLNode));
    dlNode->prior = NULL;
    DLNode *tail = dlNode;  // tail 始终指向尾结点
    DLNode *p;

    for (int i = 0; i < n; i++){
        p = (DLNode *)malloc(sizeof(DLNode));   // 初始化新结点
        p->data = a[i];
        p->prior = tail; // prior 指向前续结点
        tail->next = p; 
        tail = p;
    }
    tail->next = NULL;

    return dlNode;
}


/**
 * @description: 带头结点双链表的初始化，头插法，此方法无效，双链表无法使用头插法初始化，会出现空指针
 * 因为初始化第一个结点的时候，它的后继结点是 NULL ，NULL 结点是没有前续和后继结点的。
 * @param {*}
 * @return {*}
 */
DLNode * dlink_init_head(DLNode *dlNode, int a[], int n){
    dlNode = (DLNode *)malloc(sizeof(DLNode));  // 初始化头结点
    dlNode->prior = NULL;
    dlNode->next = NULL;
    DLNode *p;  // p 始终指向新节点
    for(int i=0; i<n; i++){
        p = (DLNode *)malloc(sizeof(DLNode)); // 初始化新结点
        p->data = a[i];
        p->next = dlNode->next;
        dlNode->next = p;
        p->prior = dlNode;
        p->next->prior = p; // 初始化第一个结点的时候，这里会出现空指针
    }
    return dlNode;
}

/**
 * @description: 在第 i 个位置上插入一个元素
 * @param {DLNode} *dlNode
 * @param {int} i
 * @param {int} val
 * @return {*}
 */
void dlink_insertElem(DLNode *dlNode, int i, int val){
    int index = 0;
    while(dlNode != NULL){
        if(index++ == i-1){
            DLNode *p = (DLNode *)malloc(sizeof(DLNode));
            p->data = val;
            DLNode *next = dlNode->next;
            dlNode->next = p;
            p->prior = dlNode;
            if(next != NULL){
                next->prior = p;
                p->next = next;
            }else{
                p->next = NULL;
            }
            break;
        }
        dlNode = dlNode->next;
    }
}


/**
 * @description: 双链表元素删除，删除第 i 个元素
 * @param {DLNode} *dlNode
 * @param {int} i
 * @return {*}
 */
void dlink_delElem(DLNode *dlNode, int i){
    int index  = 0;
    while(dlNode != NULL && dlNode->next != NULL){
        if(index++ == i-1){
            DLNode *del = dlNode->next;
            dlNode->next = del->next;
            if(del->next != NULL)  // 为 NULL 的结点不存在前驱和后续结点
                del->next->prior = dlNode;
            free(del);
            break;
        }
        dlNode = dlNode->next;
    }
}


/**
 * @description: 双链表的打印，从前往后
 * @param {DLNode} *dlNode
 * @return {*} 返回尾结点
 */
DLNode * dlink_print_head(DLNode *dlNode){
    DLNode *tail;
    printf("双链表的元素(顺序打印)：\n");
    dlNode = dlNode->next;
    while (dlNode != NULL){
        printf("%d\t",dlNode->data);
        tail = dlNode;
        dlNode = dlNode->next;
    }
    printf("\n");
    return tail;
}

/**
 * @description: 双链表的打印，从后往前，注意不要头结点
 * @param {DLNode} *dlNode
 * @return {*} 返回尾结点
 */
DLNode * dlink_print_tail(DLNode *dlNode){
    printf("双链表的元素(逆序打印)：\n");
    while (dlNode != NULL && dlNode->prior != NULL){
        printf("%d\t",dlNode->data);
        dlNode = dlNode->prior;
    }
    printf("\n");
    return dlNode;
}



/*==========================顺序栈=================================*/

/**
 * @description: 顺序栈
 * @param {*}
 * @return {*}
 */
typedef struct{
    int data[maxSize];
    int top;
}SqStack;

/**
 * @description: 顺序栈的初始化
 * @param {SqStack} *sqStack
 * @return {*}
 */
void sqStack_init(SqStack *sqStack){
    sqStack->top = 0;
}


/**
 * @description: 元素入栈
 * @param {SqStack} *sqStack
 * @param {int} val
 * @return {*}
 */
void sqStack_push(SqStack *sqStack,int val){
    if(sqStack->top < maxSize){
        sqStack->data[sqStack->top++] = val;
    }
}


/**
 * @description: 栈顶部元素出栈
 * @param {SqStack} *sqStack
 * @return {*}
 */
void sqStack_pop(SqStack *sqStack){
    if(sqStack->top > 0){
        sqStack->top--;
    }
}


/**
 * @description: 顺序栈的打印
 * @param {SqStack} *sqStack
 * @return {*}
 */
void sqStack_print(SqStack *sqStack){
    printf("顺序栈的元素：\n");
    for (int i = 0; i < sqStack->top; i++){
        printf("%d\t",sqStack->data[i]);
    }
    printf("\n");
}


/*==========================链栈（带头结点）=================================*/

/**
 * @description: 链式栈(带头结点)
 * @param {*}
 * @return {*}
 */
typedef struct LStack{
    int data;
    struct LStack *next;
}LStack;

/**
 * @description: 链栈初始化
 * @param {*}
 * @return {*}
 */
LStack * lStack_init(LStack *lStack){
    lStack = (LStack *)malloc(sizeof(LStack));
    lStack->next = NULL;
    return lStack;
}


/**
 * @description: 元素入栈，单链表头插法
 * @param {*}
 * @return {*}
 */
void lStack_push(LStack *lStack, int val){
    LStack *p;
    p = (LStack *)malloc(sizeof(LStack));
    p->data = val;
    p->next = lStack->next;
    lStack->next = p;
}


/**
 * @description: 栈顶元素出栈
 * @param {*}
 * @return {*}
 */
void lStack_pop(LStack *lStack){
    if(lStack->next != NULL){
        LStack *pop = lStack->next;
        lStack->next = pop->next;
        free(pop);
    }
}

/**
 * @description: 元素打印
 * @param {LStack} *lStack
 * @return {*}
 */
void lStack_print(LStack *lStack){
    printf("链栈元素：\n");
    lStack = lStack->next;
    while(lStack != NULL){
        printf("%d\t",lStack->data);
        lStack = lStack->next;
    }
    printf("\n");
}


/*==========================顺序(循环)队列=================================*/

// 顺序队列会产生"假溢出"，即使队列中没有了元素，但是无法让队列进队。循环队列解决了这个问题
// 同时循环队列会损失一个存储空间，否则无法区分队满与队空


/**
 * @description: 顺序队列
 * @param {*}
 * @return {*}
 */
typedef struct{
    int data[maxSize];
    int front;
    int rear;
}SqQueue;

/**
 * @description: 循环队列的初始化
 * @param {*}
 * @return {*}
 */
void sqQueue_init(SqQueue *sqQueue){
    sqQueue->front = sqQueue->rear = 0;
}


/**
 * @description: 元素入队
 * @param {sqQueue} *sqQueue
 * @param {int} val
 * @return {*}
 */
void sqQueue_enqueue(SqQueue *sqQueue, int val){
    if((sqQueue->rear+1)%maxSize != sqQueue->front){    // 队列未满
        if(sqQueue->rear == maxSize - 1){
            sqQueue->rear = 0;
        }else{
            sqQueue->rear++;
        }
        // 上面的 if else 也可简化为
        //sqQueue->rear = (sqQueue->rear+1) % maxSize;
        sqQueue->data[sqQueue->rear] = val;
    }
}

/**
 * @description: 元素出队
 * @param {SqQueue} *sqQueue
 * @return {*}
 */
void sqQueue_dequeue(SqQueue *sqQueue){
    if(sqQueue->front != sqQueue->rear){ // 队列不为空
        if(sqQueue->front == maxSize -1 ){
            sqQueue->front = 0;
        }else{
            sqQueue->front++;
        }
        // 上面的 if else 也可以简化为
        //sqQueue->front = (sqQueue->front+1) % maxSize;
    }
}


/**
 * @description: 顺序循环队列的打印，模拟队列出队，注意 front 是不存储元素的
 * @param {SqQueue} *sqQueue
 * @return {*}
 */
void sqQueue_print(SqQueue *sqQueue){
    int front = sqQueue->front;
    int rear = sqQueue->rear;
    printf("顺序队列的元素是：\n");
    while(front != rear){
        front = (front+1) % maxSize;
        printf("%d\t",sqQueue->data[front]);
    }
    printf("\n");
}


/*==========================链式队列=================================*/

/**
 * @description: 链式队列结点类型(不带头结点)
 * @param {*}
 * @return {*}
 */
typedef struct LQueueNode{
    int data;
    struct LQueueNode *next;
}LQueueNode;


/**
 * @description: 链式队列
 * @param {*}
 * @return {*}
 */
typedef struct LQueue{
    struct LQueueNode *front;   // 队首结点
    struct LQueueNode *rear;    // 队尾节点
}LQueue;



/**
 * @description: 链式队列初始化
 * @param {LQueue} *lQueue
 * @return {*}
 */
LQueue * lQueue_init(LQueue *lQueue){
    lQueue = (LQueue *)malloc(sizeof(LQueue));
    lQueue->front = lQueue->rear = NULL;
    return lQueue;
}


/**
 * @description: 元素入队
 * @param {LQueue} *lQueue
 * @param {int} data
 * @return {*}
 */
void lQueue_enqueue(LQueue *lQueue, int data){
    LQueueNode *p = (LQueueNode *)malloc(sizeof(LQueueNode));
    p->data = data;
    p->next = NULL;

    printf("元素 %d 入队\n", data);
    if(lQueue->rear == NULL){
        lQueue->front = p;
        lQueue->rear = p;
    }else{
        lQueue->rear->next = p;
        lQueue->rear = p;
    }
}

/**
 * @description: 元素出队
 * @param {LQueue} *lQueue
 * @return {*}
 */
void lQueue_dequeue(LQueue *lQueue){
    if(lQueue->front == NULL){
        lQueue->rear = NULL;
        printf("队列已空，不可出队！\n");
        return ;
    }
    printf("元素 %d 出队\n", lQueue->front->data);
    LQueueNode *front = lQueue->front;
    LQueueNode *next = front->next;
    lQueue->front = next;
    free(front);
}

/**
 * @description: 
 * @param {LQueue} *lQueue
 * @return {*} 链式队列元素的打印
 */
void lQueue_print(LQueue *lQueue){
    LQueueNode *temp = lQueue->front;
    printf("链式队列的元素是：\n");
    while(temp != NULL){
        printf("%d\t",temp->data);
        temp = temp->next;
    }
    printf("\n");
}















